C++ on MSVC講習/関数基礎
あらすじと概要
前回までで、主要な文の解説が終わりました。
今回は、関数について解説をするので、main関数から飛び出しましょう。
重要語
関数
意味や内容がまとまっている作業をひとつにまとめる機能
宣言
スコープに識別子と、その型に関する情報を導入する機能
定義
スコープに識別子と、その全ての情報を導入する機能
ODR
One Definition Rule、定義は同じスコープに1つしか書けない規則
グローバルスコープ
どのスコープにも属さない、一番外側のスコープ
()
(関数の識別子の後にあるものが)関数呼び出し演算子
引数
関数の実行時に関数へ値を渡す機能、またその渡した値
仮引数
関数の引数リスト
で宣言されている変数
実引数
関数呼び出し時に実際に渡した値
コピー渡し
実引数を仮引数にコピーして渡す方法
デフォルト引数
指定した仮引数にデフォルト値を与える機能
返り値
関数が実行終了する際に関数側から返せる値
return文
関数を終了させ、返り値を返すための文
関数オーバーロード
引数リスト
が違う、同じ名前の関数を複数定義すること
関数オーバーロードの解決
オーバーロードされた関数のうち、どれを実行するか決定すること
delete宣言
その関数を呼び出して実行してはいけないことの宣言
再帰呼び出し
ある関数が自分自身を呼び出すこと
chrono
実行時間の計測に役立つC++標準ライブラリ
関数とは何ぞや
そもそも、関数って何でしょうか。プログラミング言語としてはこうだったりしますが、
実は、数学の関数と似ている点があるため関数という名前になっています。
数学での関数
Wikipediaには、現代的には数の集合に値をとる写像の一種であると理解される。
とあります。
簡単には「2つの数による集合があった時、それぞれの集合の要素を1対1で対応させる」もの。
「ある数を与えると、何らかの規則に応じて対応する数を返す」機能があると言えるでしょう。
f(x) = x**2
としてf(2)
は4
だとか出来る見た目からすると分かりやすいと思います。
プログラミングでの関数
Wikipediaには、意味や内容がまとまっている作業をひとつの手続きとしたもの
とあります。
要するに「処理のまとまり」となるわけなんですが、引数と返り値なるものがあります。
引数は関数へ値を与えるもの、返り値は関数が実行終了時に返してくる値のことです。
おっと。こちらの関数も「引数を与えると、何らかの処理で返り値を返す」ことが出来ます。
プログラミングの関数が数学の関数と違うところ
さて、似ている点はわかりましたが、違う点はどのような所なのでしょうか。
主には、「引数/返り値が無いことがある」、「引数が同じでも状況で返り値が違う」、
「関数の実行途中に、関数以外の場所に変化を起こすことが出来る」などが存在します。
3つ目は、例えば関数が関数外の変数の値を変化させるなどできるなどが挙げられます。
何がいいのさ
関数のいい点は、大きく2つ、処理のまとまりに名前を付けることで、意味付けられること、
処理のまとまりを、引数によって記述し、汎用性を持たせられることが挙げられます。
つまり関数を用いることで、より簡潔で処理の意味が分かりやすいコードが書けます。
より簡潔で分かりやすいコードを書くことで、書く側も読む側も楽になります。
関数基礎
まずは基礎です。基礎でも非常に大量の情報量があるので頑張りましょう。
関数基礎
#include <iostream>
// addの定義
int add(int lhs, int rhs)
{
return lhs + rhs;
}
int sub(int, int); // subの宣言
int sub(int l, int r); // 宣言はいくつでも書いていい
auto void_f(void) -> void; // 後置しても前置しても返り値の型は同じ
void void_f() { return; } // (void)でも引数リスト省略でも同じ意味
int main()
{
int ans1 = add(1, 2), // add呼び出し
ans2 = sub(2, 2), // sub呼び出し
ans3 // = zero(0) // zeroは呼び出せない!
;
void_f(); // 何もしない
std::cout << "ans1 : " << ans1
<< "\nans2 : " << ans2;
}
// subの定義
int sub(int lhs, int rhs)
{
return lhs - rhs;
}
// zeroの定義
int zero(int)
{
return 0;
}
実行結果例
ans1 : 3
ans2 : 0
解説
解説です。
宣言と定義
宣言は、スコープに識別子の情報を導入しますが、型に関する情報を導入します。
そのため、識別子の区別は出来るのですが、実行ファイルにするための情報が不十分です。
実行ファイルにするための完全な情報は、宣言ではなく定義を通じて導入します。
なお、宣言はいくらでも書いてよく、一方定義は後述の通りそうではありません。
定義とODR
定義には「同じスコープで、1つの識別子の定義は必ず1つ」という、ODRがあります。
ODRのおかげで、定義は一意に定まり、複数の定義によって矛盾が生じることはありません。
ちなみに、変数は宣言しかしていないように書きましたが、実は定義だったりします。
そのため、同じ識別子を持つ変数を同じスコープに導入することが出来ないのです。
グローバルスコープと関数の定義
実は、関数は宣言は関数の中でも出来ますが、定義は関数の中では出来ません。
どのスコープにも属さない、一番外側のスコープをグローバルスコープと呼びますが、
普通の関数の定義は、グローバルスコープか名前空間で行わなければいけません。
名前空間は、名前が付いているスコープの事ですが、今後解説します。
関数
これでも難しいかもしれませんが、分かりやすくした構文は以下のようになります。
実は変数・関数の宣言はどちらも単純宣言ですが、ここでは関数について特化して示します。
構文の要素のうち、説明しないものは、他のサンプルコードを示してから説明します。
関数の宣言
返り型 識別子 (
引数リスト(opt) )
;
auto
識別子 (
引数リスト(opt) )
->
返り型 ;
関数の定義
返り型 識別子 (
引数リスト(opt) )
関数本体
auto
識別子 (
引数リスト(opt) )
->
返り型 関数本体
引数リスト
void
型名 識別子(opt) 初期化子(opt)
型名 識別子(opt) 初期化子(opt) ,
引数リスト
初期化子
=
値
=
{
値(opt) }
関数と宣言・定義
さて、関数に当てはめて理解していきましょう。
まず、構文で示しましたが、関数は関数本体
がないと宣言、あると定義となります。
宣言は型に関する情報、つまり関数だと引数リストの型の並びと返り値の型を導入します。
定義は実行ファイルにするための情報、つまり関数だと関数本体の内容も導入します。
関数の宣言・定義の方の識別子
は、変数の場合と同様の規則で命名します。
返り値と返り型
返り値は、関数が実行終了する際に関数側から返せる値で、C++では1つまでです。
返り値の型は、前置する方法と後置する方法があり、前置は先頭に書きます。
後置の場合は、先頭にはauto
を書き、)
の後に->
を置き、その後に書きます。
返り値が必要ない場合、返り値
の場所にはvoid
と書いておきます。
あまり推奨されませんが、返り型
には列挙型など、型の宣言を書くことも出来ます。
引数と引数リスト
引数は関数の実行時に関数へ値を渡す機能で、宣言・定義の引数リスト
で定義します。
引数リスト
では、1つの変数の宣言をコンマ区切りで書くように記述します。
なお返り型
とは異なり、型名
には型の宣言を書くことは出来ません。
引数が必要ない場合は、返り型
のようにvoid
を書くか、引数リスト
を省略します。
もちろん、引数リスト
で宣言された変数は、関数全体がスコープになります。
引数の識別子
変数の識別子
や関数の識別子
などと同様の規則で引数の識別子
も命名をします。
引数の識別子
が(opt)
なのは意外でしょうか。引数では識別子
は省略可能です。
実は、宣言の場合は識別子
は何ら意味を持たず、「書いてもよい」くらいの存在感です。
定義の場合は、関数本体
で使用しないのであれば、その識別子
は省略できます。
関数本体
関数本体
には、複合文を書き、複合文の中に処理のまとまり、即ち文を書きます。
既に解説しましたが、関数本体
は普通の複合文と違い、ラベルのスコープを形成します。
「関数の本体」と書いた場合は、複合文の場合の関数本体
の複合文内を指します。
return文
関数の本体では、return文を使用して、関数を終了させることが出来ます。
返り値
の型は返り型
と同じか、暗黙の変換できる関係でないといけません。
返り値が無ければreturn文自体省略でき、使用する場合は返り値
を省略して書きます。
break文と同様に、return文を実行するとそれ以降の関数本体
は実行されません。
もちろん、複数のreturn文を書くことも出来ます。構文は以下のようになります。
return文
return
返り値 ;
関数の実行と関数呼び出し演算子
関数を呼び出す際には、関数呼び出し演算子である()
を関数の識別子に続けて書きます。
引数が必要な場合は、必要な引数を()
の中に,
区切りで書くことで関数に渡せます。
渡された引数は、基本的にコピーされて引数リスト
で宣言された変数の初期化値になります。
この時、渡した引数を実引数、引数リスト
で宣言する変数を仮引数、まとめて引数といいます。
また、実引数を仮引数へとコピーして渡した時、このことをコピー渡しと呼びます。
関数の実行と返り値
関数を呼び出したとしても、やはり実際に実行されるのは評価されるときです。
関数が評価され、実行された時、結果として残るのは関数の本体が返した値です。
つまり、関数は呼び出せば単純な、返り型
の値として扱うことが出来ます。
直接的な解説1 - add
関数
add
関数は、その名の通り加算を行う関数で、引数に取った2つのint値を加算して返却します。
add
関数は、main関数で使用する前に定義しているため問題ありません。
ちなみに、lhs/rhs
は、left/right hand side
で、左辺/右辺
などの意味を持ちます。
直接的な解説2 - add
/sub
関数
sub
関数も、やはりその名の通り減算を行う関数で、add
の逆のような存在です。
sub
関数は、main関数で使用する前に宣言をし、main関数の後で定義をするため大丈夫。
解説通り、宣言の引数リスト
の名前は意味をなさないので、定義と異なっています。
直接的な解説3 - void_f
関数
void_f
関数は、引数も返り値も全くない、マジで何もしないシュールな関数です。
解説通り、返り値はvoid
で無いことを示し、もちろん前置しても後置しても同じ型です。
わざと宣言も定義もしていますが、実際は定義だけで問題ありません。
ただ、こんな関数は実際に書く場合はただただ要らない関数なので関係ありませんが。
直接的な解説4 - zero
関数
zero
関数は、main関数で使う前に宣言・定義共に行われていません。
つまり、main関数でzero
関数を使用すると、コンパイラは「それ何?」でエラーです。
解説通り、関数の本体で仮引数を使用しない場合、引数の識別子
は省略できます。
直接的な解説5 - main関数内
main関数内では、関数をいくつか呼び出しています。
解説通り、呼び出すときは関数呼び出し演算子たる()
を使用します。
引数は()
の間に,
で渡し、関数が引数を取らない場合であれば何も書きません。
返り値はリテラルなどの値と同様に使用できるので、変数の初期化に使っています。
関数とスコープ
関数とスコープについてです。初期化子
はここで説明します。
関数とスコープ
#include <iostream>
int add(int, int); // ok
int add(int = 10, int = 20); // ok, 後からデフォルト引数を付けることが出来る
int add(int, int); // ok
// int add(int, int = 30); // ng, デフォルト引数の再定義は出来ない
// int add(int = 10, int = 20); // ng, デフォルト引数が完全に一致しても再定義になる
// int sum(int = 10, int, int = 10) // ng, デフォルト引数が末尾に並んでいない
int main()
{
int num;
std::cout << "1 : " << add() << " " << add(10) << " " << add(10, 20) << "\n";
// main関数のスコープでaddを宣言
int add(int, int = 20); num = add(10);
std::cout << "2 : " << num << " " << add(10, 20) << "\n";
{
// main関数の複合文のスコープでaddを宣言
int add(int, int), num = add(10, 20);
std::cout << "3 : " << num << "\n";
{
// 対応する定義がないadd関数の宣言
// main関数の複合のスコープで宣言されたadd関数を隠す
short add(short, short);
// shortの方のadd関数は、対応する定義が無いので使えない
// std::cout << "4 : " << add(10, 20) << "\n";
// sub関数の宣言、定義はmain関数の後に後置
int sub(int = 60, int = 30), dummy();
std::cout << "4 : " << sub() << " " << dummy() << "\n";
}
}
}
int add(int lhs, int rhs)
{
return lhs + rhs;
}
int sub(int lhs = 50, int rhs = 30)
{
return lhs - rhs;
}
int dummy()
{
// dummy関数からはsub関数の定義のデフォルト引数が使える
return sub();
}
実行結果
1 : 30 30 30
2 : 30 30
3 : 30
4 : 30 20
解説
変数の時のスコープと似ていますね。解説です。
関数と宣言・定義
関数の宣言と定義を復習すると、宣言はいくら書いてもよく、関数内にも書けるけれど、
定義はODRによって1つのみ、そして関数の中にネストして書くことは出来ませんでした。
宣言して使っている関数も、全体として定義が無ければエラーになるのは注意が必要です。
関数とスコープ
そして、変数同様に、関数も識別子を持つので、識別子を使えるコード上の範囲があります。
この時の、「識別子を使えるコード上の範囲を制限するもの」がスコープでした。
識別子は、宣言又は定義によってそのスコープに導入されてから、終わりまで使用出来ます。
関数の宣言とスコープ
変数はより内側のスコープで宣言することで、外側の変数を隠すことが出来ました。
これは、関数でも同様に、より内側のスコープでの宣言で外側の関数を隠すことが出来ます。
ここで問題になるのが、外側の関数を隠した内側の関数の定義が存在するかどうかです。
内側のスコープの宣言と紐づけられる定義が存在しなければ、エラーになってしまいます。
初期化子
とデフォルト引数
ここで、関数の宣言・定義の構文の、引数リストの初期化子
について解説します。
初期化子
は、仮引数に指定することで、その仮引数にデフォルト値を与える機能です。
初期化子
を用いて、デフォルト値を与えられた仮引数をデフォルト引数と言います。
初期化子
の形式
構文でも示していますが、引数リスト
の初期化子
は=
を使った形で値
を与えます。
変数の宣言の時の初期化子
の時と比べ、使えるものが減っていることに注意しましょう。
また、初期化子
は識別子
が無かったとしても書くことが出来ます。
デフォルト引数の制限
デフォルト引数は、必ず引数リスト
の末尾(右端)にまとまっていないといけません。
言い換えれば、デフォルト引数よりも末尾(右側)の方に通常の引数は置いてはいけません。
つまり、(int, int = 0)
、(int = 0, int = 0)
、(int, int, int = 0)
などは正しく、
(int = 0, int)
や(int = 0, int, int = 0)
などはエラーになるということです。
デフォルト引数がある関数の呼び出し
デフォルト引数がある関数は、存在する数の分だけ実引数を減らしても呼び出しが出来ます。
足りない実引数については、デフォルト引数に指定されているデフォルト値で埋められます。
もちろん、デフォルト引数に明示的に実引数を渡しても関数呼び出しが出来ます。
例えば(int, int = 0, int = 0)
という関数を(0)
/(0, 0)
/(0, 0, 0)
などで呼び出せます。
デフォルト引数のやっかいなところ
デフォルト引数は、関数の宣言・定義を通して1度のみしか定義してはならないのです。
そして、全く同じデフォルト引数であったとしても、例外ではなく書くことは出来ません。
ただし、外側のを内側のスコープで隠す場合は、その内側の宣言で上書き状態になります。
直接的な解説1 - add
関数
またadd
関数ですが、今回のadd
関数も同じような定義ですが、定義は後置しています。
add
関数は、2番目の宣言でデフォルト引数を付けているので、それ以降は付けられません。
ただしスコープが違うので、main関数やその複合文で宣言するadd
関数は違っています。
しかし、main関数の複合文の複合文のadd
関数は、対応する定義が無いので使えません。
直接的な解説2 - sub
関数
sub
関数は使用する前に宣言をしているので、定義がmain関数後でも使用できています。
そして、使用時に指定されて使用されたデフォルト引数は、明らかに直前の宣言です。
定義の方のデフォルト引数は、定義以降に書いた関数からなら使用することが出来ます。
直接的な解説3 - dummy
関数
dummy
関数は、sub
関数の定義で指定されているデフォルト引数が、
それ以降で使用できることを示すために用意したダミー関数です。
dummy
関数も、sub
関数同様に使う直前に宣言をして使用しています。
直接的な解説4 - main関数内
main関数内では、1~4
まで4つの場所に分けて出力をしています。
1~3
では、呼び出し可能な引数の渡し方を全種類試しています。
概ね、変数の場合と同様ですが、関数の宣言がころころ変わっています。
1~4
での、それぞれの関数の宣言は以下のようになります。
1~4
での関数の宣言(add
関数)
1
int add(int = 10, int 20)
グローバルスコープ
2
int add(int, int = 20)
main関数のスコープ
3
int add(int, int)
main関数の複合文のスコープ
4
short add(short, short)
main関数の複合文の複合文のスコープ
(対応する定義なし)
1~4
での関数の宣言(sub
/dummy
関数)
1
なし
2
なし
3
なし
4
int sub(int = 60, int = 30)
int dummy()
main関数の複合文の複合文のスコープ
関数標準
関数オーバーロード(多重定義)や再帰についてです。
関数本体
のdelete
の方もここで解説します。
関数標準
#include <iostream>
#include <chrono>
int add(int, int);
long add(long, long) = delete;
long long add(long long, long long);
double add(double, double);
unsigned long long fac(unsigned n)
{
if (n == 0 || n == 1)
{
return 1;
}
if (n > 20)
{
return 0;
}
return n * fac(n - 1);
}
unsigned long long fib(unsigned n)
{
if (n == 0)
{
return 0;
}
if (n == 1 || n == 2)
{
return 1;
}
if (n > 93)
{
return 0;
}
return fib(n - 1) + fib(n - 2);
}
int main()
{
std::cout << "int : " << add(10, 10)
<< "\nlong long : " << add(10ll, 10ll)
<< "\ndouble : " << add(1.111, 1.111);
// add(10l, 10l); // ng, 削除された関数にオーバーロード解決されたので呼び出せない!
// add(10, 10l); // ng, int版とlong版との「近さ」が一致、どちらを呼び出せばいいかわからない!
// add(10, 10ll); // ng, 同様!
// add(10l, 10ll); // ng, 同様!
unsigned n; std::cin >> n;
{
std::cout << "\n\nNの階乗(0 <= N <= 20)を求めます\n";
std::cout << fac(n) << "\n";
}
std::cin >> n;
{
std::cout << "\n\nフィボナッチ数列の第N項(0 <= N <= 93)を求めます\n";
auto start = std::chrono::system_clock::now();
std::cout << fib(n) << "\n";
auto end = std::chrono::system_clock::now();
std::cout << "計算に" << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "msかかりました。";
}
}
int add(int lhs, int rhs)
{
return lhs + rhs;
}
long long add(long long, long long)
{
// あれ?
return 0ll;
}
double add(double lhs, double rhs)
{
return lhs + rhs;
}
補足
今回は、実行時間を計りたかったので、標準ライブラリのchrono
を使用しています。
ほとんどこの書き方が定型であるなどするので、あまり解説しません。
実行結果例1
int : 20
long long : 0
double : 2.222
Nの階乗(0 <= N <= 20)を求めます
$ 1
1
フィボナッチ数列の第N項(0 <= N <= 93)を求めます
$ 50
12586269025
計算に36550msかかりました。
実行結果例2
int : 20
long long : 0
double : 2.222
Nの階乗(0 <= N <= 20)を求めます
$ 20
2432902008176640000
フィボナッチ数列の第N項(0 <= N <= 93)を求めます
$ 60
1548008755920
計算に4488028msかかりました。
解説
再帰呼び出し、難しいですから今理解しなくていいかもしれません。
解説です。
関数オーバーロード(多重定義)
C++では、引数リスト
が違えば、同じ名前の関数を多重定義することが出来ます。
この機能のことを関数オーバーロード、あるいは関数の多重定義と呼びます。
この機能によって、複数の型に対して同じ名前で関数を提供することが出来ます。
なお、多重定義出来ないC言語では、型ごとに名前が少し違う関数が多数存在します。
関数オーバーロードの解決
オーバーロードされた関数を呼び出すときには、どの関数を呼び出すかの解決がされます。
オーバーロード解決は、大きく3つのフェーズで、複雑なルールに基づいて解決されます。
大筋としては、一番実引数の並びに近い引数リスト
を持つ関数が呼び出されます。
ただし、その「近さ」が同じであるような関数が複数存在すると解決は失敗し、エラーです。
例を見せてくれ
オーバーロード解決には返り値は関係ないので、引数リスト
のみで例を示します。
f(int),f(double)
でf(0),f(0ll),f(0.0)
なら、f(int),/*失敗*/,f(double)
になります。
2
番目は、どちらに対しても「暗黙の型変換が1回」の「近さ」なのでエラーになります。
delete宣言
関数本体
にはdelete
の方は、指定した関数を呼び出してはいけないことを示します。
delete宣言された関数は、呼び出してはいけず、呼び出した場合にはエラーが発生します。
つまり、オーバーロード解決の結果、delete宣言された関数に解決するとエラーになります。
デフォルト引数と関数オーバーロード
当然、オーバーロードしている関数は名前は同じこそ、別々の関数です。
したがって、デフォルト引数もそれぞれに対して別のデフォルト引数を置けます。
ただ、デフォルト引数の数が違う場合は、呼び出す関数が何なのか、注意が必要です。
int f(int, int = 0), f(long, long)
となっていて、f(0l)
と呼び出したとすれば
f(0l)
はint f(int, int = 0)
に解決されて、エラーが出ることはありません。
これは、2
フェーズ目にf(long, long)
は実引数が足りず、候補から外されるからです。
関数の再帰呼び出し
C++の関数は、ある関数が自分自身を呼び出す、再帰呼び出しをすることが出来ます。
再帰呼び出しする関数のことを再帰関数などともよび、すごいループとして扱います。
再帰呼び出しの例としてよく挙げられる、階乗とフィボナッチ数列を用意しました。
n
の階乗は1~n
を掛けた、1!=1, 2!=1*2=2 ,3!=1*2*3
のようなものです。
フィボナッチ数列は、前回の練習問題で説明したので、説明は省きます。
再帰呼び出しとreturn
再帰呼び出しは、単純に関数の本体で、自分自身を呼び出すことを指します。
そのため、別にreturn文の返り値
の場所に限られたりはしていません。
なお、再帰呼び出しの場合だけ、返り値がない関数でも返り値
が書けます。
つまり、void f() { return f(); }
ということが出来ます。
再帰呼び出しの考え方
再帰呼び出しは、ベースケースと再帰ケースに分けて考えることが多いです。
ベースケースとは、1
の階乗や、フィボナッチ数列の第1,2
項のことを言います。
つまり、再帰呼び出しをしない、定義されていて値が決まっているようなケースです。
一方、再帰ケースは、2
以降の階乗や、フィボナッチ数列の第3
項以降です。
つまり、再帰呼び出しを行って計算する必要がある、ベースケース以外のケースです。
全ての再帰ケースは、他の再帰ケースを辿るなどしてベースケースに辿り着くようにします。
ベースケースと再帰ケースの実装
それぞれのケースの分け方は、単純にif文などで分岐すれば問題ありません。
ベースケースは再帰呼び出しをしないケースなので、先にチェックしてreturnしましょう。
すなわち、再帰呼び出し部分を実行しないようにして、再帰呼び出しを止めます。
ベースケースで再帰呼び出しを止めないなどすると、一生再帰呼び出しするので注意です。
再帰呼び出しの良い所
良い所は、なんといっても単純に複数のケースの値を得て計算できることでしょう。
フィボナッチ数列は、ループだと2つ変数を用意して、注意深く実装する必要があります。
再帰呼び出しでは、単純に1/2
前の項を再帰呼び出しで得ることが出来るので楽です。
つまり、関数にしたことで、セマンティクス(意味論)が分かりやすいことや、
数学的な定義(漸化式のことですが)を直感的に実装できる点で優秀です。
再帰呼び出しの悪い所
しかし、何と言っても再帰呼び出しは計算リソースを無駄に使うことが多いです。
フィボナッチ数列の場合なら、f(6)
の時点で24
回もの関数呼び出しが行われます。
これについては、Qiitaの記事の表が分かりやすいですが、f(6)
がf(5)/f(4)
を、
それがf(4)/f(3),f(3)/f(2)
を、それがf(3)/f(2),f(2)/f(1),f(2)/f(1),f(1)/f(0)
を…
のように、既に呼び出した事のある関数を、何度も被って再帰呼び出ししてしまうのです。
悪い所がもろバレ
悪い所がもろバレするのが、今回はfib
関数である、フィボナッチ数列の再帰関数実装です。
実行結果を見てもらうとわかりますが、f(50)
で36.5
秒、f(60)
で4488
秒かかります。
そう、何度も被って再帰呼び出しした分のせいで、かなり実行に時間がかかっています。
前回の練習問題の方の、for文実装は0.001
秒程度で処理できるので、明らかです。
対策
遅くなってしまうのは、既に指摘しているように、無駄な再帰呼び出しがあるからです。
1度呼び出したケースの結果を保持すれば、無駄なの再帰呼び出しは省けます。
この時には、今後解説する配列などを使用して結果を保持すると良いでしょう。
この無駄な再帰呼び出しを防ぐ方法を、メモ化再帰と呼んだりするようです。
あるいは、そもそも再帰呼び出しを使わずに、ループで処理しても無駄が省けます。
実行時間計測
実行時間計測には、標準ライブラリのchrono
が便利です。#include <chrono>
しましょう。
計測開始と計測終了の時刻を、std::chrono::system_clock::now()
で入手します。
そしてその差をstd::chrono::duration_cast
関数の引数に入れることで整えます。
呼び出すときには、std::chrono::duration_cast<型名>
と書いて時間の単位を指定します。
この<型名>
と書いているのは、今後解説するテンプレートという機能のものです。
その関数の返り値に.count()
と書いて値を入手、それでstd::cout
に出力できます。
主にstd::chrono::duration_cast
の型名
に指定できる型は以下のようになっています。
時間単位
に指定できる型
ナノ秒(-1e9秒)
std::chrono::nanoseconds
マイクロ秒(-1e6秒)
std::chrono::microseconds
ミリ秒(-1e3秒)
std::chrono::milliseconds
秒
std::chrono::seconds
分
std::chrono::minutes
時
std::chrono::hours
変数の宣言のauto
時間計測の計測開始と計測終了の時刻を変数で持つ時、型名
をauto
と書きました。
このauto
は、初期化の値に応じて、変数の型を決定する、型推論を意味します。
std::chrono::duration_cast
関数が返す返り値の型は長いので使っています。
現在主に使っている、組み込み型などは型名は短いので、auto
を使う意味は薄いです。
また、今後解説する機能の参照などが付く場合があるので、今は使わないでおきましょう。
直接的な解説1 - add
関数の宣言と定義
やっぱりadd
関数ですが、int/long long/double版があり、long版はdelete宣言です。
つまり、long版を呼び出してしまうとエラーになってしまう、ということです。
また、long long版のadd
関数は、常に0
を返す、バグだらけの関数になっています。
直接的な解説2 - add
関数呼び出し
オーバーロード解決は、完全に引数リスト
と一致する呼び出しがあればそれが最優先、
完全に一致しなかった場合は、暗黙の型変換で変換して呼び出せるかなど「近さ」を
考え、1番「近い」関数がただ1つに定まった時のみ解決し、それ以外はエラーです。
オーバーロード解決の結果、delete宣言された関数が選ばれてもエラーなので注意しましょう。
直接的な解説3 - fac
関数
fac
関数は、階乗を求める関数で、引数の値の階乗を求めて値を返します。
MSVCはunsigned long long
が64bitの非負整数なので、21
の階乗は表せません。
そのため、21
以上の階乗を求めさせられた場合は、無条件で0
を返しています。
直接的な解説4 - fac
関数の再帰呼び出し
階乗の定義から、0/1
の階乗は1
として返し、これがベースケースになります。
2
以上の階乗は、再帰ケースになるので、再帰呼び出しして行きます。
例えば、fac(5)
の場合であれば、以下のように関数が再帰呼び出しし、結果が返されます。
fac(5) = 5*fac(4) = 5*4*fac(3) = 5*4*3*fac(2) = 5*4*3*2*fac(1) = 5*4*3*2*1 = 120
直接的な解説5 - fib
関数
fib
関数は、フィボナッチ数列を求める関数で、第引数項を求めて値を返します。
例によって、MSVCのunsigned long long
は第94
項以降は表せません。
そのため、第94
項以降を求めさせられた場合は、無条件で0
を返します。
ただし、実行結果例のように、数が大きくなると現実的な時間では計算出来ません。
直接的な解説6 - fib
関数の再帰呼び出し
フィボナッチ数列の定義から、第1/2
項は1
とし、これがベースケースになります。
今回は、第0
項を求めるのはエラーだという仕様にしたので、第0
項は0
が返されます。
第3
項以降は、再帰ケースになるので、再帰呼び出ししていきます。
Qiitaの記事の表を参照してもらった方が分かりやすいので推奨ですが、
例えばfib(4)
の場合であれば、以下のように再帰呼び出しをし、結果が返されます。
fib(4) = 4*fib(3)*fib(2) = 3*fib(2)*fib(1)*fib(1)*fib(0) = 4*3*2*1*1*1 = 24
参照、出典
参照や出典です
参照
[dcl.fct]
https://timsong-cpp.github.io/cppwp/n4861/dcl.fct
[dcl.fct.def]
https://timsong-cpp.github.io/cppwp/n4861/dcl.fct.def
[dcl.fct.default]
https://timsong-cpp.github.io/cppwp/n4861/dcl.fct.default
[over]
https://timsong-cpp.github.io/cppwp/n4861/over
宣言 - cppreference.com
https://ja.cppreference.com/w/cpp/language/declarations
関数 - cppreference.com
https://ja.cppreference.com/w/cpp/language/functions
関数宣言 - cppreference.com
https://ja.cppreference.com/w/cpp/language/function
定義と ODR - cppreference.com
https://ja.cppreference.com/w/cpp/language/definition
関数のdefault/delete宣言 - cpprefjp C++日本語リファレンス
https://cpprefjp.github.io/lang/cpp11/defaulted_and_deleted_functions.html
オーバーロード解決 - cppreference.com
https://ja.cppreference.com/w/cpp/language/overload_resolution
関数の創世から深淵まで駆け抜ける関数とはなんぞや講座 - Qiita
https://qiita.com/yumetodo/items/cdfb41781d32d98be1b4
再帰関数を学ぶと、どんな世界が広がるか - Qiita
https://qiita.com/drken/items/23a4f604fa3f505dd5ad